pip install plotly
from collections import defaultdict
from typing import List, Set, Tuple
from fractions import Fraction
def edges_to_vertices(edges: List[Tuple]) -> List[int]:
vertices = []
for edge in edges:
for vertex in edge:
if vertex not in vertices:
vertices.append(vertex)
return vertices
def compute_interior_angle(n_sides: int) -> Fraction:
return Fraction(1, 2) - Fraction(1, n_sides)
class NotEnoughRoomError(Exception):
pass
def getitem(data):
lst = list(data)
if len(lst) > 1:
raise ValueError(data)
return lst[0]
class NoMovesError(Exception):
pass
class ImpossibleError(Exception):
pass
class Tiling:
def __init__(self, pattern):
self.pattern = pattern
self.shapes = []
self.edges_to_shapes = defaultdict(lambda : [])
self.vertices_to_edges = defaultdict(lambda : [])
self.next_new_vertex = 0
def list_possible_shapes(self, vertex: int) -> List[int]:
edges = self.vertices_to_edges[vertex]
shape_ids = set.union(*[set(self.edges_to_shapes[edge]) for edge in edges])
angle_sum = 0
remaining_pattern = list(self.pattern)
for shape_id in shape_ids:
shape = self.shapes[shape_id]
angle_sum += shape["angle"]
remaining_pattern.pop(remaining_pattern.index(shape["n_sides"]))
required_angle = sum([compute_interior_angle(n_sides) for n_sides in remaining_pattern])
if angle_sum + required_angle > 1:
raise NotEnoughRoomError(vertex)
return remaining_pattern
def add_first_shape(self, n_sides):
if len(self.shapes) > 0:
raise RuntimeError("already initialised")
edges = []
for k in range(n_sides - 1):
edges.append((k, k + 1))
edges.append((0, k + 1))
self._add_shape(edges)
def add_shape_to_edge(self, n_sides: int, edge: Tuple, debug=False):
edges = self.compute_new_edges(n_sides, edge, debug=debug)
self._add_shape(edges)
def _add_shape(self, edges: List[Tuple]):
n_sides = len(edges)
vertices = []
shape_id = len(self.shapes) # next shape
for edge in edges:
self.edges_to_shapes[edge].append(shape_id)
for vertex in edge:
self.vertices_to_edges[vertex].append(edge)
vertices = edges_to_vertices(edges)
self.shapes.append({
"edges": edges,
"vertices": vertices,
"angle": compute_interior_angle(n_sides),
"n_sides": n_sides,
})
self.next_new_vertex = max(max(vertices) + 1, self.next_new_vertex)
def list_open_edges(self, vertex, ignore_vertices=()):
return [
edge for edge in self.vertices_to_edges[vertex]
if len(self.edges_to_shapes[edge]) == 1
if edge[0] not in ignore_vertices
if edge[1] not in ignore_vertices
]
def get_possible_shapes_for_edge(self, edge) -> List[int]:
possible_shapes0 = self.list_possible_shapes(edge[0])
possible_shapes1 = self.list_possible_shapes(edge[1])
set_possible_shapes = set(possible_shapes0) & set(possible_shapes1)
return list(set_possible_shapes)
def compute_new_edges(self, n_sides, base_edge, debug=False):
vertices = list(base_edge) # order matters, describes adjacency
edges = [base_edge]
new_vertex = self.next_new_vertex
if debug:
breakpoint()
allow_new_vertex = False
while len(vertices) < n_sides:
this_vertex = vertices[-1]
open_edges = self.list_open_edges(this_vertex, ignore_vertices=[vertices[-2]]) # ignore inside vertex
# no pre-existing edge
if not open_edges:
if allow_new_vertex:
next_vertex = new_vertex
new_vertex += 1
else:
# try the other direction first
vertices = list(reversed(vertices))
allow_new_vertex = True
continue
# a pre-existing edge exists
elif len(open_edges) == 1:
# this edge is part of the new shape
if len(self.list_possible_shapes(this_vertex)) == 1:
next_vertex = getitem([v for v in open_edges[0] if v != this_vertex])
next_vertex_shapes = self.list_possible_shapes(next_vertex)
assert n_sides in next_vertex_shapes, f"could not place sides={n_sides} at vertex={next_vertex}"
# There will be more new shapes between this new shape and the
# pre-existing edge.
# NOTE: This assumes that there are only ever two open edges on any vertex.
# This is (hopefully) guaranteed by:
# - building breadth-first
# - always attaching new shapes to at least one pre-existing edge
else:
if allow_new_vertex:
next_vertex = new_vertex
new_vertex += 1
else:
# try the other direction first
vertices = list(reversed(vertices))
allow_new_vertex = True
continue
# should be impossible
else:
raise ValueError(f"too many open edges on vertex={this_vertex}")
vertices.append(next_vertex)
allow_new_vertex = False
# Next time, add on the other side.
# If we only built from one side, it would be really hard to tell
# if we should connect to adajacent open edges on the far side
vertices = list(reversed(vertices))
edges.append(tuple(sorted([this_vertex, next_vertex])))
# close the shape
edges.append(tuple(sorted([vertices[0], vertices[-1]])))
assert len(edges) == n_sides # sanity check!
return edges
def iter_open_edges(self):
for edge in self.edges_to_shapes: # breadth-first
if len(self.edges_to_shapes[edge]) == 2:
# this edge already has two shapes attached
continue
yield edge
def run(self, n_steps, debug=False):
counter = 0
while counter < n_steps:
saved_n_sides = None
saved_edge = None
for edge in self.iter_open_edges(): # breadth-first
possible_shapes = self.get_possible_shapes_for_edge(edge)
if len(possible_shapes) == 1:
n_sides = possible_shapes.pop()
# always pick the smallest avaliable shape to avoid non-local interactions
if n_sides == min(self.pattern):
saved_n_sides = n_sides
saved_edge = edge
break
elif saved_n_sides is None:
saved_n_sides = n_sides
saved_edge = edge
continue
elif n_sides < saved_n_sides:
saved_n_sides = n_sides
saved_edge = edge
continue
elif len(possible_shapes) == 0:
raise ImpossibleError(edge)
if saved_n_sides is None:
raise NoMovesError
else:
self.add_shape_to_edge(saved_n_sides, saved_edge, debug=debug)
counter += 1
import math
import plotly
def iter_vertices_on_edges(base_edge, edges):
remaining_edges = set(edges)
remaining_edges.remove(base_edge)
# v0 = previous vertex
# v1 = pivot vertex
# v2 = next vertex
# arbitrarily pick base_edge[1] as pivot
v0, v1 = base_edge
while remaining_edges:
next_edge = getitem([
e for e in remaining_edges
if v1 in e
])
v2 = getitem([v for v in next_edge if v != v1])
yield v0, v1, v2, next_edge
remaining_edges.remove(next_edge)
v0, v1 = v1, v2
class Plot:
def __init__(self, tiling):
self.vertices_to_coords = {
0: (0, 0),
1: (1, 0),
}
self.edges = [(0, 1)]
self.rendered_shapes = {}
for shape_id, shape_info in enumerate(tiling.shapes):
edges = shape_info["edges"]
base_edge = edges[0] # first edge is always shared edge with shape on which this shape is bolted onto
assert base_edge in self.edges
theta = math.pi - shape_info["angle"] * 2 * math.pi
if shape_id > 0:
adjacent_shape_id = getitem([
s for s in tiling.edges_to_shapes[base_edge]
if s != shape_id
])
adjacent_shape_edges = tiling.shapes[adjacent_shape_id]["edges"]
v0, v1, v2, _ = next(iter_vertices_on_edges(base_edge, adjacent_shape_edges))
x0, y0 = self.vertices_to_coords[v0]
x1, y1 = self.vertices_to_coords[v1]
x2, y2 = self.vertices_to_coords[v2]
x1hat, y1hat = x1 - x0, y1 - y0
x2hat, y2hat = x2 - x0, y2 - y0
n_x1hat, n_y1hat = -y1hat, x1hat # anti-clockwise normal
if n_x1hat * x2hat + n_y1hat * y2hat < 0: # i.e. adjacent shape turns clockwise
# NB dot product can't be zero because turning angle < 180 for all regular polygons
# make anti-clockwise turns
theta *= -1
for v0, v1, v2, edge in iter_vertices_on_edges(base_edge, edges):
assert v0 in self.vertices_to_coords
assert v1 in self.vertices_to_coords
if edge in self.edges:
continue
elif v2 in self.vertices_to_coords:
self.edges.append(edge)
continue
x0, y0 = self.vertices_to_coords[v0]
x1, y1 = self.vertices_to_coords[v1]
# shift origin to (x0, y0)
x1hat, y1hat = x1 - x0, y1 - y0
# rotate theta from (x0, y0)
x2hat = x1hat * (math.cos(theta) + 1) + y1hat * math.sin(theta)
y2hat = - x1hat * math.sin(theta) + y1hat * (math.cos(theta) + 1)
# back to global coords
x2, y2 = x2hat + x0, y2hat + y0
self.edges.append(edge)
self.vertices_to_coords[v2] = (x2, y2)
self.rendered_shapes[shape_id] = edges
def plotly_iplot(self, label_vertices=False):
text = []
x = []
y = []
for v, (x_, y_) in self.vertices_to_coords.items():
text.append(f"<b>{v}</b>")
x.append(x_)
y.append(y_)
fig = {
"data": [
{
"type": "scatter", "x": x, "y": y,
"mode": "markers+text" if label_vertices else "markers", "name": "",
"text": text, "hovertemplate": "%{text}",
"textposition": "top right",
"textfont_size": 12
},
],
"layout": {
"xaxis": dict(
zeroline=False, showticklabels=False, ticks="", showgrid=False,
# tickmode = 'linear', dtick = 0.5
),
"yaxis": dict(
scaleanchor="x", scaleratio=1,
zeroline=False, showticklabels=False, ticks="", showgrid=False,
# tickmode = 'linear', dtick = 0.5,
),
"shapes": [
{
'line': {'color': 'RoyalBlue', 'width': 3},
'type': 'line',
'x0': self.vertices_to_coords[v0][0], 'x1': self.vertices_to_coords[v1][0],
'y0': self.vertices_to_coords[v0][1], 'y1': self.vertices_to_coords[v1][1],
'xref': 'x', 'yref': 'y'
}
for (v0, v1) in self.edges
],
"height": 800,
"width": 800,
},
}
plotly.offline.iplot(fig)
tiling = Tiling([12, 4, 3, 3])
tiling.add_first_shape(4)
tiling.add_shape_to_edge(3, (0, 1))
tiling.add_shape_to_edge(3, (1, 2))
tiling.run(23)
# tiling.add_shape_to_edge(3, (2, 5))
# tiling.run(7)
plot = Plot(tiling)
plot.plotly_iplot(True)
tiling = Tiling([12, 4, 3, 3])
tiling.add_first_shape(4)
tiling.add_shape_to_edge(12, (0, 1))
tiling.run(8)
plot = Plot(tiling)
plot.plotly_iplot(True)
tiling = Tiling([12, 4, 3, 3])
tiling.add_first_shape(4)
tiling.add_shape_to_edge(12, (0, 1))
tiling.add_shape_to_edge(12, (2, 3))
tiling.run(4)
plot = Plot(tiling)
plot.plotly_iplot(True)
tiling = Tiling([6, 6, 3, 3])
tiling.add_first_shape(6)
tiling.add_shape_to_edge(3, (0, 1))
tiling.add_shape_to_edge(6, (1, 2))
tiling.run(35)
plot = Plot(tiling)
plot.plotly_iplot()
tiling = Tiling([6, 6, 3, 3])
tiling.add_first_shape(6)
tiling.add_shape_to_edge(3, (0, 1))
tiling.add_shape_to_edge(3, (1, 2))
tiling.add_shape_to_edge(3, (2, 3))
tiling.add_shape_to_edge(3, (3, 4))
tiling.add_shape_to_edge(3, (4, 5))
tiling.add_shape_to_edge(3, (0, 5))
tiling.run(12)
plot = Plot(tiling)
plot.plotly_iplot()
tiling = Tiling([4, 4, 4, 4])
tiling.add_first_shape(4)
tiling.run(100)
plot = Plot(tiling)
plot.plotly_iplot()
tiling = Tiling([3, 12, 12])
tiling.add_first_shape(3)
tiling.run(25)
plot = Plot(tiling)
plot.plotly_iplot()
tiling = Tiling([4, 8, 8])
tiling.add_first_shape(4)
tiling.run(100)
plot = Plot(tiling)
plot.plotly_iplot()
tiling = Tiling([6, 4, 12])
tiling.add_first_shape(12)
tiling.add_shape_to_edge(4, (0, 1))
tiling.add_shape_to_edge(6, (1, 2))
tiling.run(102)
plot = Plot(tiling)
plot.plotly_iplot()
tiling = Tiling([6, 6, 6])
tiling.add_first_shape(6)
tiling.run(101)
plot = Plot(tiling)
plot.plotly_iplot()
tiling = Tiling([6, 3, 3, 3, 3])
tiling.add_first_shape(6)
tiling.add_shape_to_edge(3, (0, 1))
tiling.add_shape_to_edge(3, (1, 6))
tiling.add_shape_to_edge(6, (6, 7))
tiling.run(300)
plot = Plot(tiling)
plot.plotly_iplot()
tiling = Tiling([6, 3, 3, 3, 3])
tiling.add_first_shape(6)
tiling.add_shape_to_edge(3, (0, 1))
tiling.add_shape_to_edge(3, (0, 6))
tiling.add_shape_to_edge(6, (6, 7))
tiling.run(300)
plot = Plot(tiling)
plot.plotly_iplot()
tiling = Tiling([3, 3, 3, 4, 4])
tiling.add_first_shape(4)
tiling.add_shape_to_edge(4, (0, 1))
tiling.run(6)
plot = Plot(tiling)
plot.plotly_iplot()
tiling = Tiling([3, 3, 3, 4, 4])
tiling.add_first_shape(4)
tiling.add_shape_to_edge(3, (0, 1))
tiling.add_shape_to_edge(3, (1, 2))
tiling.add_shape_to_edge(3, (2, 3))
tiling.add_shape_to_edge(4, (1, 4))
tiling.add_shape_to_edge(4, (0, 4))
tiling.run(5)
plot = Plot(tiling)
plot.plotly_iplot()
tiling = Tiling([3, 3, 3, 3, 3, 3])
tiling.add_first_shape(3)
tiling.run(150)
plot = Plot(tiling)
plot.plotly_iplot()
def meta_tiling(tiling, n_steps, update_func):
n = 0
while n < n_steps:
try:
tiling.run(1)
except NoMovesError:
print(f"hit {update_func.__name__} on move={n}")
update_func(tiling)
n += 1
def tri_on_hex(tiling: Tiling):
for edge in tiling.iter_open_edges():
shape_id = getitem(tiling.edges_to_shapes[edge])
shape_info = tiling.shapes[shape_id]
if shape_info["n_sides"] == 6:
if 3 in tiling.get_possible_shapes_for_edge(edge):
tiling.add_shape_to_edge(3, edge)
return
raise NoMovesError
tiling = Tiling([6, 6, 3, 3])
tiling.add_first_shape(6)
meta_tiling(tiling, 192, tri_on_hex)
plot = Plot(tiling)
plot.plotly_iplot()
def hex_on_hex(tiling: Tiling):
for edge in tiling.iter_open_edges():
shape_id = getitem(tiling.edges_to_shapes[edge])
shape_info = tiling.shapes[shape_id]
if shape_info["n_sides"] == 6:
if 6 in tiling.get_possible_shapes_for_edge(edge):
tiling.add_shape_to_edge(6, edge)
return
raise NoMovesError
tiling = Tiling([6, 6, 3, 3])
tiling.add_first_shape(6)
meta_tiling(tiling, 23, hex_on_hex)
plot = Plot(tiling)
plot.plotly_iplot()
tiling = Tiling([6, 6, 3, 3])
tiling.add_first_shape(6)
meta_tiling(tiling, 10, tri_on_hex)
meta_tiling(tiling, 20, hex_on_hex)
# meta_tiling(tiling, 200, tri_on_hex)
while True:
try:
tri_on_hex(tiling)
except NoMovesError:
break
meta_tiling(tiling, 80, tri_on_hex)
plot = Plot(tiling)
plot.plotly_iplot()
def single_sq_6443(tiling: Tiling):
for edge in tiling.iter_open_edges():
shape_id = getitem(tiling.edges_to_shapes[edge])
shape_info = tiling.shapes[shape_id]
if shape_info["n_sides"] == 4:
possible_shapes = tiling.get_possible_shapes_for_edge(edge)
possible_shapes = set(possible_shapes) - {4}
if len(possible_shapes) == 1:
tiling.add_shape_to_edge(possible_shapes.pop(), edge)
return
for edge in tiling.iter_open_edges():
shape_id = getitem(tiling.edges_to_shapes[edge])
shape_info = tiling.shapes[shape_id]
if shape_info["n_sides"] == 6:
if 4 in tiling.get_possible_shapes_for_edge(edge):
tiling.add_shape_to_edge(4, edge)
return
raise NoMovesError
tiling = Tiling([6, 4, 4, 3])
tiling.add_first_shape(6)
meta_tiling(tiling, 200, single_sq_6443)
# tiling.add_shape_to_edge(4, (12,13))
# tiling.run(6)
plot = Plot(tiling)
plot.plotly_iplot()
def many_sq_6443(tiling: Tiling):
for edge in tiling.iter_open_edges():
shape_id = getitem(tiling.edges_to_shapes[edge])
shape_info = tiling.shapes[shape_id]
if shape_info["n_sides"] == 4:
if 4 in tiling.get_possible_shapes_for_edge(edge):
tiling.add_shape_to_edge(4, edge)
return
for edge in tiling.iter_open_edges():
shape_id = getitem(tiling.edges_to_shapes[edge])
shape_info = tiling.shapes[shape_id]
if shape_info["n_sides"] == 6:
if 4 in tiling.get_possible_shapes_for_edge(edge):
tiling.add_shape_to_edge(4, edge)
return
raise NoMovesError
tiling = Tiling([6, 4, 4, 3])
tiling.add_first_shape(6)
meta_tiling(tiling, 200, many_sq_6443)
# tiling.add_shape_to_edge(4, (12,13))
# tiling.run(6)
plot = Plot(tiling)
plot.plotly_iplot()
def double_sq_6443(tiling: Tiling):
for edge in tiling.iter_open_edges():
shape_id = getitem(tiling.edges_to_shapes[edge])
shape_info = tiling.shapes[shape_id]
if shape_info["n_sides"] == 4:
for shape_edge in shape_info["edges"]:
adjacent_shape_sides = [
tiling.shapes[s_id]["n_sides"] for s_id in tiling.edges_to_shapes[shape_edge]
if s_id != shape_id
]
if adjacent_shape_sides == [4]:
possible_shapes = set(tiling.get_possible_shapes_for_edge(edge)) - {4}
if len(possible_shapes) == 1:
tiling.add_shape_to_edge(possible_shapes.pop(), edge)
return
# no adjacent square
if 4 in tiling.get_possible_shapes_for_edge(edge):
tiling.add_shape_to_edge(4, edge)
return
raise NoMovesError
tiling = Tiling([6, 4, 4, 3])
tiling.add_first_shape(6)
tiling.add_shape_to_edge(4, (0, 1))
# tiling.add_shape_to_edge(4, (6, 7))
meta_tiling(tiling, 250, double_sq_6443)
plot = Plot(tiling)
plot.plotly_iplot()
tiling = Tiling([6, 4, 4, 3])
tiling.add_first_shape(6)
meta_tiling(tiling, 100, single_sq_6443)
meta_tiling(tiling, 500, many_sq_6443)
# tiling.add_shape_to_edge(4, (12,13))
# tiling.run(6)
plot = Plot(tiling)
plot.plotly_iplot()
tiling = Tiling([6, 4, 4, 3])
tiling.add_first_shape(6)
meta_tiling(tiling, 50, many_sq_6443)
meta_tiling(tiling, 200, single_sq_6443)
meta_tiling(tiling, 300, double_sq_6443)
# tiling.add_shape_to_edge(4, (12,13))
# tiling.run(6)
plot = Plot(tiling)
plot.plotly_iplot()
import random
def random_shape(tiling: Tiling):
edges = list(tiling.iter_open_edges())
random.seed(tuple(edges))
edge = random.choice(edges)
possible_shapes = tiling.get_possible_shapes_for_edge(edge)
n_sides = random.choice(possible_shapes)
tiling.add_shape_to_edge(n_sides, edge)
tiling = Tiling([6, 4, 4, 3])
tiling.add_first_shape(6)
meta_tiling(tiling, 250, random_shape)
plot = Plot(tiling)
plot.plotly_iplot()
def many_square(tiling):
for edge in tiling.iter_open_edges():
shape_id = getitem(tiling.edges_to_shapes[edge])
shape_info = tiling.shapes[shape_id]
if shape_info["n_sides"] == 4:
if 4 in tiling.get_possible_shapes_for_edge(edge):
tiling.add_shape_to_edge(4, edge)
return
tiling = Tiling([3, 3, 3, 4, 4])
tiling.add_first_shape(4)
meta_tiling(tiling, 297, many_square)
plot = Plot(tiling)
plot.plotly_iplot()
def single_square(tiling):
for edge in tiling.iter_open_edges():
shape_id = getitem(tiling.edges_to_shapes[edge])
shape_info = tiling.shapes[shape_id]
if shape_info["n_sides"] == 4:
possible_sides = set(tiling.get_possible_shapes_for_edge(edge)) - {4}
if len(possible_sides) == 1:
tiling.add_shape_to_edge(possible_sides.pop(), edge)
return
elif 3 in tiling.get_possible_shapes_for_edge(edge):
tiling.add_shape_to_edge(3, edge)
return
raise NoMovesError
tiling = Tiling([3, 3, 3, 4, 4])
tiling.add_first_shape(4)
meta_tiling(tiling, 100, single_square)
plot = Plot(tiling)
plot.plotly_iplot()
def double_tri(tiling: Tiling):
for edge in tiling.iter_open_edges():
shape_id = getitem(tiling.edges_to_shapes[edge])
shape_info = tiling.shapes[shape_id]
if shape_info["n_sides"] == 3:
for shape_edge in shape_info["edges"]:
adjacent_shape_sides = [
tiling.shapes[s_id]["n_sides"] for s_id in tiling.edges_to_shapes[shape_edge]
if s_id != shape_id
]
if adjacent_shape_sides == [3]:
possible_shapes = set(tiling.get_possible_shapes_for_edge(edge)) - {3}
if len(possible_shapes) == 1:
tiling.add_shape_to_edge(possible_shapes.pop(), edge)
return
if 3 in tiling.get_possible_shapes_for_edge(edge):
tiling.add_shape_to_edge(3, edge)
return
raise NoMovesError
tiling = Tiling([3, 3, 3, 4, 4])
tiling.add_first_shape(4)
meta_tiling(tiling, 100, double_tri)
plot = Plot(tiling)
plot.plotly_iplot()
tiling = Tiling([3, 3, 3, 4, 4])
tiling.add_first_shape(4)
tiling.add_shape_to_edge(3, (0, 1))
tiling.add_shape_to_edge(4, (0, 4))
meta_tiling(tiling, 200, random_shape)
plot = Plot(tiling)
plot.plotly_iplot()